1687C - Sanae and Giant Robot - CodeForces Solution

/*
           _                   _         _       __  __  _____ 
     /\   | |            /\   | |       | |     |  \/  |/ ____|
    /  \  | |__   ___   /  \  | |__   __| | ___ | \  / | |     
   / /\ \ | '_ \ / _ \ / /\ \ | '_ \ / _` |/ _ \| |\/| | |     
  / ____ \| |_) | (_) / ____ \| |_) | (_| | (_) | |  | | |____ 
 /_/    \_\_.__/ \___/_/    \_\_.__/ \__,_|\___/|_|  |_|\_____|
*/

// build command:
// g++ -std=gnu++17 -O3 -DDEBUG -g -fsanitize=signed-integer-overflow -fsanitize=bounds-strict -fsanitize=address -fsanitize=integer-divide-by-zero -fsanitize=float-divide-by-zero -fsanitize=pointer-overflow -fsanitize=shift-exponent -fsplit-stack -Wshadow -Wall -fconcepts -Wno-unused-result

// REMEMBER:
// BS, Offline, Persistent SegTree, SQRT, Treap, MaxFlow, FFT, Matrices

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")

// DEBUG STUFF
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#ifdef DEBUG
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif


#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

// RANDOM NUMBER GENERATOR
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());  
#define SHUF(v) shuffle(all(v), RNG); 
// Use mt19937_64 for 64 bit random numbers.

int getrand(int l,int r) {
	return uniform_int_distribution<int>(l, r)(RNG);
}

const ld eps = 1e-9;
const int mod = 1e9 + 7;
const int oo = 1e9 + 7;
const ll lloo = 1e18 + 7;
const int N = 1e6 + 7;

int n,m,a[N],b[N];
ll pref[N];

struct DSU {
	vector<int> par, rnk, sz, left, right;
	vector<set<int>*> st;
	int c;

	DSU(int n) : c(n+1) {
		rnk.resize(n+1);
		par.resize(n+1);
		sz.resize(n+1);
		left.resize(n+1);
		right.resize(n+1);
		st.resize(n+1);
		for (int i = 0; i <= n; ++i) {
			par[i] = i;
			left[i] = right[i] = i;
			st[i] = new set<int>;
		}
	}
	int find(int i) {
		return (par[i] == i ? i : find(par[i]));
	}
	bool same(int i, int j) {
		return find(i) == find(j);
	}
	int get_size(int i) {
		return sz[find(i)];
	}
	int count() {
		return c;    //connected components
	}
	int merge(int i, int j) {
		if ((i = find(i)) == (j = find(j))) return -1;
		else --c;
		if (rnk[i] > rnk[j]) swap(i, j);
		par[i] = j;
		sz[j] += sz[i];
		left[j] = min(left[j],left[i]);
		right[j] = max(right[j],right[i]);
		
		if (st[i]->size() > st[j]->size()) swap(st[i],st[j]);
		
		for(auto x:*st[i]) st[j]->insert(x);
		
		if (rnk[i] == rnk[j]) {rnk[j]++;}
		return j;
	}
};

DSU dsu(1);
set<int> st;
void dfs(int l,int r) {
	//dbg(l,r);
	if (dsu.same(l,r)) return;
	int u = dsu.find(l);
	while(dsu.right[u] < r) {
		st.insert(u);
		st.insert(dsu.right[u]+1);
		u = dsu.merge(u,dsu.right[u]+1);
	}
	int L = l,R = r;
	
	auto it = dsu.st[u]->upper_bound(r);
	
	while(it != dsu.st[u]->end()) {
		int x = *it;
		if (st.count(x)) L = min(L,x),R = max(R,x);
		it++;
	}
	
	it = dsu.st[u]->lower_bound(l);
	
	while(it != dsu.st[u]->begin()) {
		int x = *it;
		if (st.count(x)) L = min(L,x),R = max(R,x);
		it--;
	}
	
	int x = *it;
		if (st.count(x)) L = min(L,x),R = max(R,x);
	
	dfs(L,R);
}

void solve(int tc) {
	cin >> n >> m;
	dsu = DSU(n);
	st.clear();
	st.insert(0);
	//dbg("YES");
	for(int i = 1 ; i <= n ; i++) cin >> a[i];
	for(int i = 1 ; i <= n ; i++) {
		cin >> b[i];
		pref[i] = (pref[i-1])+a[i]-b[i];
		if (pref[i] == 0) st.insert(i);
	}
	//dbg("YES");
	vector<pii> nodes;

	for(int i = 0 ; i < m ; i++) {
		int l,r;
		cin >> l >> r;
		l--;
		dsu.st[l]->insert(r);
		dsu.st[r]->insert(l);
		
		if (pref[l] == pref[r] && pref[l] == 0) {
			nodes.pb({l,r});
		}
	}

	for(int i = 1 ; i <= n ; i++) {
		if (pref[i] == pref[i-1] && pref[i] == 0) dsu.merge(i,i-1);
	}

	for(auto [l,r]:nodes) {
		dfs(l,r);
	}

	cout << (dsu.count() == 1?"YES":"NO") << '\n';
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	// freopen("in","r",stdin);
	// freopen("out","w",stdout);
	int T = 1;
	cin >> T;
	for(int i = 0 ; i < T ; i++) solve(i+1);
	return 0;
}